This invention pertains generally to digital imaging, and more particularly to digital image scrambling.
Digital images, including digital video, are often communicated or distributed over non-private channels, such as satellite links, cable television networks, wireless home networks, and the Internet. Conditional access systems for private digital image/video transmission or storage are a necessity for many applications, for example, pay-TV, confidential videoconferences, confidential facsimile transmissions, and medical image transmission and storage in a database. Digital cryptography techniques must be used in conjunction with non-private channels if unauthorized parties are to be prevented from gaining access to such private imagery.
Video scramblers are commonly employed to prevent unauthorized access to image data. Several video scrambling systems rely on methods of directly distorting the visual image data such that, without descrambling, the video appears unintelligible to a viewer. For example, U.S. Pat. No. 4,100,374, issued Jul. 11, 1978, to N. Jayant and S. Kak, and entitled xe2x80x9cUniform permutation privacy systemxe2x80x9d, describes an approach where a video signal is divided into groups of N successive video samples, and samples within a group are then permuted. U.S. Pat. No. 5,321,748, entitled xe2x80x9cMethod and apparatus for television signal scrambling using block shufflingxe2x80x9d, issued Jun. 14, 1994, to D. Zeidler and J. Griffin, describes an alternate approach where blocks of video lines and lines within a block are shuffled. In U.S. Pat. No. 5,815,572, entitled xe2x80x9cVideo scramblingxe2x80x9d, and issued Sep. 29, 1998, to G. Hobbs, the approach includes a combination of video permutation modes, including line reversal, line inversion, line permutation and block (of lines) permutation, where the combination of modes used changes as time progresses. These methods have several drawbacks, including: 1) they can severely degrade the compressibility of the images; and 2) they are vulnerable to code-breaking attacks because of the highly spatially-and temporally-correlated nature of video sequences.
In many systems for scrambling digital images, the images are first subject to compression, and then the compressed image data is treated as ordinary data and is encrypted/decrypted using traditional cryptographic algorithms such as the Digital Encryption Standard (DES). See H. Pinder and M. Palgon, xe2x80x9cApparatus and method for cipher stealing when encrypting MPEG transport packets,xe2x80x9d U.S. Pat. No. 5,684,876, Nov. 4, 1997; N. Katta et. al, xe2x80x9cScrambled transmission system,xe2x80x9d U.S. Pat. No. 5,621,799, Apr. 15, 1997. Due to the high data rate of video (even compressed video), these methods add a large amount of processing overhead to meet a real-time video delivery requirement. To reduce the amount of processing overhead, several researchers have proposed selective encryption of MPEG compressed video data. See T. Maples and G. Spanos, xe2x80x9cPerformance study of a selective encryption scheme for the security of networked, real-time video,xe2x80x9d Proc. 4th Inter. Conf. Computer Communications and Networks, Las Vegas, Nev. (September 1995); J. Meyer and F. Gadegast, xe2x80x9cSecurity mechanisms for multimedia data with the example MPEG-1 video,xe2x80x9d http://www.cs.tuberlin.de/phade/phade/secmpeg.html (1995). For example, in selective encryption, only the entropy-coded I frames, or the entropy-coded I frames and Intra-coded blocks of predictive (P/B) frames may be encrypted. I. Agi and L. Gong showed in xe2x80x9cAn empirical study of secure MPEG video transmissions,xe2x80x9d The Internet Society Symposium on Network and Distributed System Security (February 1996), that in some cases the encryption of I frames alone does not provide sufficient security. These systems may also be vulnerable to possible plain text attacks that make use of the known synchronization word or End of Block symbol that are often used in compression systems to limit error propagation. To selectively encrypt some segments of the compressed data such as Intra blocks sometimes incurs additional header overhead to locate such segments (see, e.g., Meyer and Gadegast""s method). In addition, this classical approach is not very secure for transcoding at intermediate routers of the transmission channel because the transcoder must be able to decrypt.
Other systems use more elaborate means to distort video images. B. Macq and J. Quisquater propose, in xe2x80x9cDigital images multiresolution encryptionxe2x80x9d, J. Interactive Multimedia Assoc. Intell. Property Proj., vol. 1, no. 1, pp. 179-186 (January 1994), a three-step process for scrambling an image. The image is first transformed by a xe2x80x9cLinear Multiresolution Transformxe2x80x9d (LMT) proposed by the authors. Selected rows and columns of the transformed image are then shuffled. The shuffled transform image is then subjected to an inverse LMT prior to transform and bitstream coding. A decoder reverses these steps to restore the original image. Although this method is less vulnerable to code-breaking attacks, and can provide a level of transparency (e.g., a degraded version of the original image is visible in the scrambled signal), it still has disadvantagesxe2x80x94the two additional transforms required at each end add complexity, and image compressibility is still adversely affected.
One researcher proposes performing one or more of a group of shuffling operations on the Discrete Cosine Transform (DCT) coefficients of an image. L. Tang, xe2x80x9cMethods for encrypting and decrypting MPEG video data efficiently,xe2x80x9d Proc. The Fourth ACM International Multimedia Conference (ACM Multimedia ""96), pp. 219-229, scrambles each of the 8xc3x978 blocks of DCT coefficients obtained during MPEG transform coding, before the coefficients are input to the MPEG entropy coder. This scrambling may entail 1) shuffling the AC coefficients within each block, 2) shuffling the AC coefficients using two shuffle tables (with a second random variable determining which shuffle table to apply to each block), 3) grouping the DC coefficients from eight blocks and encrypting the group with DES, and 4) splitting the DC coefficient from each block into two DC bit patterns, placing one of these in the last AC coefficient position of the block, and then scrambling all coefficients for the block. Although these techniques are not complex and provide a reasonable level of security, they change the statistical properties (e.g., the run-length characteristics) of the DCT coefficients. As a result, they may increase the bit rate of the compressed video by as much as 50%. This approach is also not very secure for transcoding at intermediate routers because the cryptographic key is needed to decrypt before requantization.
It is recognized herein that digital image encryption presents a set of issues, aside from security, that are unique in the data cryptography field. A digital image scrambling scheme should have a relatively simple implementation, amenable to low-cost decoding equipment and low-delay requirement for real-time interactive applications. It should have a minimum adverse impact on the compressibility of the image. It should preferably be independent of the bitstream compression selected for the image, and allow compression transcoding without decryption. It should provide good overall security, although it may also be preferable in some systems to allow non-authorized users a level of transparency, both to entice them to pay for full transparency, and to discourage code-breaking.
The present invention provides digital image scrambling that meets the objectives outlined above. It is apparently the first digital image scrambling approach that can meet each of these objectives without compromise. Preferably, the invention accomplishes these objectives by operating on transformed images, prior to Huffman, run-length, arithmetic, embedded, or other entropy coding. The encryption/decryption operations performed by the invention are designed to preserve, as much as possible, the transformed image properties that allow entropy coders to efficiently compress an image. And the preferred encryption operations are computationally inexpensive operations, such as block shuffling and bit-scrambling on a subset of bits.
In accordance with a first aspect of the invention, a method of encrypting a digital image is disclosed. The method includes applying a space-frequency transform to the image, thereby generating a transform coefficient map. The map is then encrypted using one or more encryption techniques selected from the following: scrambling the sign bits of the coefficients in the map; scrambling the refinement bits of the coefficients; partitioning the map into a set of two-dimensional coefficient blocks and shuffling selected blocks within the map; and grouping a set of transform coefficients from a spatial frequency subband and shuffling the transform coefficients within the group.
In a second aspect of the invention, several methods of encrypting a digital image are disclosed. In one method, a group of bits are selected across a block of data, the group having lower than average predicted compressibility, as compared to the predicted compressibility of the block of data as a whole. These bits are then scrambled. In a second method, a motion-compensation data component of a digital video stream is selectively scrambled.
In accordance with another aspect of the invention, an image encryption system is disclosed. The system comprises an encryption buffer that accepts transformed image data, along with at least one encryption subsystem operating on transform data stored in the buffer. The subsystem(s) can include a sign bit scrambler, a block shuffler, a block rotator, and a subband coefficient shuffler. The system may further comprise a quantizer and/or an entropy coder that operates on encrypted transform data.
In a further aspect of the invention, an encrypted image decryption system is disclosed. The system comprises a decryption buffer that accepts encrypted transform data, along with at least one decryption subsystem operating on encrypted transform data stored in the buffer. The subsystem(s) can include a sign bit descrambler, a block deshuffler, a block derotator, and a subband coefficient deshuffler. The system may further comprise an entropy decoder and/or a dequantizer that operates on entropy coded encrypted transform data.